package _greedy

import org.junit.Assert
import org.junit.Test

/*
https://programmercarl.com/0455.%E5%88%86%E5%8F%91%E9%A5%BC%E5%B9%B2.html
https://leetcode.cn/problems/assign-cookies/

455. 分发饼干
示例 1:
输入: g = [1,2,3], s = [1,1]
输出: 1

示例 2:
输入: g = [1,2], s = [1,2,3]
输出: 2
 */
class leetcode_455 {
    @Test
    fun test_1() {
        val actual = findContentChildren(intArrayOf(1, 2, 3), intArrayOf(1, 1))
        val expect = 1
        Assert.assertEquals(expect, actual)
    }

    @Test
    fun test_2() {
        val actual = findContentChildren(intArrayOf(1, 2), intArrayOf(1, 2, 3))
        val expect = 2
        Assert.assertEquals(expect, actual)
    }

    @Test
    fun test_3() {
        val actual = findContentChildren(intArrayOf(1, 2), intArrayOf(1, 1, 3))
        val expect = 2
        Assert.assertEquals(expect, actual)
    }

    fun findContentChildren(g: IntArray, s: IntArray): Int {
        /*
        贪心
        1 先用小便干满足
        2 先排序
        3 外层循环是胃口值
         */

        g.sort()
        s.sort()

        var index: Int = 0
        for (i in 0 until s.size) {
            if (index < g.size && g[index] <= s[i]) {
                index++
            }
        }
        return index
    }
}